{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "桶排序"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Bucket_Sort(a, bucketcount):\n",
    "    minvalue, maxvalue = min(a), max(a)\n",
    "    bucketsize = (maxvalue - minvalue + 1) // bucketcount\n",
    "    res = [[] for i in range(bucketcount+1)]\n",
    "    for x in a:\n",
    "        idx = (x - minvalue) // bucketsize\n",
    "        res[idx].append(x)\n",
    "    ans = []\n",
    "    for res_x in res:\n",
    "        res_x.sort()\n",
    "        ans += res_x\n",
    "    return ans\n",
    "n = int(input())\n",
    "a = list(map(int, input().split()))\n",
    "a = Bucket_Sort(a,min(1000, n))\n",
    "print(' '.join(map(str, a)))"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
